package algorithm;

import java.util.Arrays;

/**
 * Created by Administrator on 2017/7/7.
 */
public class QuickSort {
    public static int[] quickSort(int[] target,int left,int right){
        if (left < right){
        int base_index = partition(target,left,right);
        quickSort(target,left,base_index-1);
        quickSort(target,base_index+1,right);
        return target;
        }
        return target;
    }

    public static int partition(int[] target,int left,int right){
        int base = target[left];
        int base_index = left;

        for (int i = left+1; i <=right ; i++) {
            if (base>target[i]){
                base_index++;
                if (base_index != i){
                    int temp = target[base_index];
                    target[base_index] = target[i];
                    target[i] = temp;
                }
            }
        }

        target[left] = target[base_index];
        target[base_index] = base;
        Arrays.toString(target);
        return base_index;
    }

    public static void main(String[] args) {
        int[] teaser = {4,5,8,12,4,65,33,21,13,78,99};
        int[] sorted = quickSort(teaser,0,teaser.length-1);
        Arrays.toString(sorted);
    }
}
